package month1;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LruCache146_04 {
    public static void main(String[] args) {

    }


}

/**
 * 双链表
 */
class LRUCache {
    Map<Integer, Node> cache;
    int capacity;

    DoubleList dl;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        dl = new DoubleList();
    }

    public int get(int key) {
        Node value = cache.get(key);
        if (value != null) {
            dl.move2Head(value);
        }
        return  value == null ? -1 : value.value;
    }

    public void put(int key, int value) {
        Node val = cache.get(key);
        if (val != null) {
            val.value = value;
            dl.move2Head(val);
            return;
        }
        val = new Node(key, value);
        if (cache.size() == capacity) {
            Node node = dl.removeTail();
            cache.remove(node.key);
        }
        dl.add2Head(val);
        cache.put(key, val);
    }

    static class Node {
        int key, value;
        Node pre, next;

        Node() {
        }

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    static class DoubleList {
        Node head, tail;

        DoubleList() {
            tail = new Node();
            head = new Node();
            tail.pre = head;
            head.next = tail;
        }

        void move2Head(Node node) {
            removeNode(node);
            add2Head(node);
        }

        Node removeTail() {
            Node pre = tail.pre;
            removeNode(pre);
            return pre;
        }

        void removeNode(Node node) {
          node.next.pre = node.pre;
          node.pre.next = node.next;
          node.next = null;
          node.pre = null;
        }

        void add2Head(Node node) {
            node.next = head.next;
            node.pre = head;
            head.next.pre = node;
            head.next = node;
        }

    }
}
